package com.likou;

import java.util.ArrayList;
import java.util.List;

public class q22 {
    List<String> ans = new ArrayList<>();
    String string = "";

    public List<String> generateParenthesis(int n) {
        DFS(n, 0, 0);

        return ans;
    }

    private void DFS(int n, int left, int right) {
        if (left == n && right == n) {
            ans.add(string);
            return;
        }

        if (left < n) {
            String temp = string;
            string = string + "(";
            DFS(n, left + 1, right);
            string = temp;
        }

        if (left > right) {
            String temp = string;
            string = string + ")";
            DFS(n, left, right + 1);
            string = temp;
        }
    }
}
